10548. Найти правильный размен

 

В древние времена люди вместо денег обменивались товарами. В наличии имеются два типа товаров: A и B. Покупатель желает приобрести товар на сумму c > 0. Стоимости товаров A и B соответственно равны a и b. Если одно из значений a или b отрицательно, то продавец может этим товаром давать сдачу. Одновременно отрицательными a и b быть не могут. Сколькими способами покупатель может приобрести товар на сумму c, если это возможно?

 

Вход. Первая строка содержит количество тестов n (0 < n < 1001). Каждая следующая строка содержит три числа a, b и c (0 < |a|, |b|, |c| < 231).

 

Выход. Для каждого теста вывести количество комбинаций, которыми покупатель может приобрести товар ровно  на сумму c. Если приобрести товар невозможно, то вывести сообщение “Impossible”. Если число комбинаций бесконечно, то вывести “Infinitely many solutions”.

 

Пример входа

3
2 3 15
2 –3 5
10 36 7

 

Пример выхода

3
Infinitely many solutions
Impossible

 

 

РЕШЕНИЕ

расширенный алгоритм Евклида

 

Анализ алгоритма

Если покупатель получит x штук товара A и y штук товара B, заплатив при этом сумму c, то получим уравнение ax + by = c. Уравнение имеет решения тогда и только тогда, когда c делится на НОД(a, b).

Лемма. Если (x0, y0) – одно из решений уравнения ax + by = c, то все его решения имеют вид (x0 + kb, y0 – ka), где k – целое число. Очевидно, что a(x0 + kb) + b(y0 – ka) = ax0 + by0 = c.

Если одно из значений a или b отрицательно, то уравнение ax + by = c имеет бесконечно много решений. Действительно, если (x0, y0) – решение, то пара (x0 + kb, y0 – ka) будет также решением для любого целого отрицательного k, для которого y0 – ka ³ 0 (если b < 0) или для любого натурального k, для которого x0 + kb ³ 0 (если a < 0).

Если решение существует и оба значения a и b положительны, сокращаем a, b, c на их общий делитель и при помощи расширенного алгоритма Евклида находим x’, y’, для которых ax’ + by’ = 1. Помножив последнее равенство на c и положив x0 = cx’ и y0 = cy’, получим пару (x0, y0), являющуюся решением уравнения ax + by = c.

Из леммы следует, что все решения уравнения имеют вид (x0 + kb, y0 – ka), где k – целое число. Поскольку в задаче решения должны быть неотрицательными, то имеют место следующие неравенства: x0 + kb ³ 0, y0 – ka ³ 0. Откуда имеем следующие ограничения: k ³ , k £ . Количество решений  уравнения ax + by = c, для которых x ³ 0, y ³ 0, равно  –  + 1.

 

Пример

Рассмотрим первый тест, где следует найти количество решений уравнения 2x + 3y = 15 в целых числах. Числа 2 и 3 взаимно простые, находим x’и y’, для которых 2x’ + 3y’ = 1. Из расширенного алгоритма Евклида имеем: x’ = -1, y’ = 1. Помножив их на 15, получим x0 = 15x’ = -15, y0 = 15y’ = 15. Имея одно решение (x0, y0) = (-15, 15), можно описать множество всех решений исходного уравнения согласно выше приведенной лемме: x = -15 + 3k, y = 15 – 2k. Оба значения должны быть неотрицательными, следовательно -15 + 3k ³ 0,  y = 15 – 2k ³ 0. Или то же самое что 3k ³ 15,  15 ³ 2k. Откуда k ³ = 5, k £  = 7. Объединяя ограничения на k, получим: 5 £ k £ 7. То есть существует 3 варианта размена: 15 = 2 * 0 + 3 * 5 (k = 5, x = 0, y = 5), 15 = 2 * 3 + 3 * 3 (k = 6, x = 3, y = 3), 15 = 2 * 6 + 3 * 1 (k = 7, x = 6, y = 1).

Для второго теста имеем уравнение 2x – 3y = 5. Одним из его решений будет x0 = 1, y0 = -1. Все множество решений описывается формулой: x = 1 – 3k, y = -1 – 2k. Для всех отрицательных k значения x и y будут положительными, и удовлетворять условию задачи.

Для третьего теста решений не существует, так как для любых натуральных x и y значение 10x + 36y всегда четно и не может равняться 7.

 

Реализация алгоритма

При вычислении используем 64-битовый целый тип long long. Для простоты использования переопределим тип:

 

typedef long long i64;

 

Вычисление наибольшего общего делителя:

 

i64 gcd(i64 a, i64 b)

{

  return (!a) ? b : gcd(b % a, a);

}

 

Расширенный алгоритм Евклида имеет вид:

 

void gcdext(i64 a,i64 b, i64 *d, i64 *x, i64 *y)

{

  i64 s;

  if (b == 0)

  {

    *d = a; *x = 1; *y = 0;

    return;

  }

  gcdext(b,a % b,d,x,y);

  s = *y;

  *y = *x - (a / b) * (*y);

  *x = s;

}

 

Читаем количество тестов n. Для каждого теста читаем a, b, c.

 

scanf("%lld",&n);

for(i = 0; i < n; i++)

{

  scanf("%lld %lld %lld",&a,&b,&c);

 

Вычисляем наибольший общий делитель d чисел a и b. Если c не делится на d, то выводим сообщении о невозможности произведения размена.

 

  d = gcd(a,b);

  if (c % d > 0)

  {

    printf("Impossible\n");

    continue;

  }

 

Если a или b отрицательно, то существует бесконечно много вариантов произведения размена.

 

  if ((a < 0) || (b < 0))

  {

    printf("Infinitely many solutions\n");

    continue;

  }

 

Сокращаем входные значения a, b, c на их общий делитель d. Запускаем процедуру расширенного алгоритма Евклида и находим пару (x, y) – решение уравнения ax + by = c.

 

  a /= d; b /= d; c /= d;

  gcdext(a,b,&d,&x,&y);

  x *= c; y *= c;

 

Ищем нижнюю kmin и верхнюю kmax границы для переменной k, откуда и получаем количество решений уравнения ax + by = c. Поскольку a, b, x, y – целые, то чтобы не потерять точность вычислений, помножим дроби –x / b и y / a на действительное число 1.0.

 

  kmin = (i64)ceil(-1.0*x / b); kmax = (i64)floor(1.0*y / a);

  res = (i64)kmax - kmin + 1;

 

Если значение res не равно нулю, то выводим его. Иначе печатаем сообщение о том, что произвести размен невозможно.

 

  if (res) printf("%lld\n",res);    

      else printf("Impossible\n");

}